package leetcode.editor.cn.q1_300.q100;

import java.util.Arrays;

/**
 * 用四周没有被围绕的 O 去感染，没有被感染到的就是需要改为 X 的
 *
 * @author qidi
 * @date 2022-01-12 10:13:47
 */
class Q0130_SurroundedRegions {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void solve(char[][] board) {
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                if (board[i][0] == 'O') infect(i, 0, board);
                if (board[i][n - 1] == 'O') infect(i, n - 1, board);
            }

            for (int i = 0; i < n; i++) {
                if (board[0][i] == 'O') infect(0, i, board);
                if (board[m - 1][i] == 'O') infect(m - 1, i, board);
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'X') continue;
                    if (board[i][j] == 'O') board[i][j] = 'X';
                    if (board[i][j] == 'o') board[i][j] = 'O';
                }
            }
        }

        private void infect(int i, int j, char[][] board) {
            if (i < 0 || i == board.length || j < 0 || j == board[0].length) return;

            if (board[i][j] == 'O') {
                board[i][j] = 'o';
                infect(i - 1, j, board);
                infect(i + 1, j, board);
                infect(i, j - 1, board);
                infect(i, j + 1, board);
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0130_SurroundedRegions().new Solution();
        char[][] chars = null;
        chars = new char[][]{{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}};
        solution.solve(chars);
        for (int i = 0; i < chars.length; i++) {
            System.out.println(Arrays.toString(chars[i]));
        }
        System.out.println("====================");
        chars = new char[][]{{'O', 'O'}, {'O', 'O'}};
        solution.solve(chars);
        for (int i = 0; i < chars.length; i++) {
            System.out.println(Arrays.toString(chars[i]));
        }
    }
}